/**
 * 有一个正整数和负整数组成的NxN矩阵，
 * 请编写代码找出元素总和最大的子矩阵。请尝试使用一个高效算法。
 * 给定一个int矩阵mat和矩阵的阶数n，请返回元素总和最大的子矩阵的元素之和
 */
public class SubMatrix {
	int maxSum = Integer.MIN_VALUE;

	//核心思想，先求出行或列为主的子矩阵的最大值
	//再将这个行或列压缩成一个元素，即它的最大值
	//再取另外一种主序列的值，即将二维数组分解成了两次的一维数组求最大
	public int sumOfSubMatrix(int[][] mat, int n) {

		int sum[] = new int[mat[0].length];
		for (int i = 0; i < mat.length; i++) {//压缩的起点
			for (int j = 0; j < sum.length; j++) sum[j] = 0;//每次更换起点sum就重置，感觉还可改进
			for (int t = 0; t < mat.length - i; t++) {//步长，矩阵=起点+步长
				for (int j = 0; j < sum.length; j++) sum[j] += mat[i + t][j];//求上述矩阵的压缩和
				maxSum = Math.max(maxSum, getMaxSum(sum)); //压缩为一维求和，取最大值              
			}
		}
		return maxSum;
	}

	public int getMaxSum(int a[]) {//常用，一维数组中连续子数组的最大和int maxSum = Integer.MIN_VALUE;
		int curSum = 0;
		for (int i = 0; i < a.length; i++) {
			curSum += a[i];
			maxSum = Math.max(maxSum, curSum);
			if (curSum < 0) curSum = 0;
		}
		return maxSum;
	}

	public static void main(String[] args) {
		int[][] mat = {
				{-10, 1},
				{-15, 24}
		};
		SubMatrix subMatrix = new SubMatrix();
		System.out.println(subMatrix.sumOfSubMatrix(mat, 2));
	}
}
